/*
============================================================================
 Name        : dd_vector.c
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_vector.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_vector.h"


#define __DD_DEFAULT_VEC_SIZE	8 


static void _expand_to(dd_vector* vec, DD_INT size)
{
	if ( vec && vec->count < size ) {
		void** pre_ptr = vec->ptr ;
		vec->ptr = (void**)DD_MALLOC(size * sizeof(void*)) ;
		DD_MEMCPY( vec->ptr, pre_ptr, vec->count * sizeof(void*) ) ;
		vec->alloc_size = size ;
		__do_destroy(pre_ptr) ;
	}
}


dd_vector* dd_vector_create(DD_INT granularity) 
{
	dd_vector* vec		= (dd_vector*)DD_MALLOC(sizeof(dd_vector)) ;
	vec->granularity	= (granularity > 0) ? granularity : __DD_DEFAULT_VEC_SIZE ;
	vec->ptr			= (void**)DD_MALLOC(vec->granularity * sizeof(void*)) ;
	vec->count			= 0 ;
	vec->alloc_size		= vec->granularity ;
	return vec ;
}

void dd_vector_destroy(dd_vector* vec, void (*free_fun)(void*)) 
{
	if(vec) {
		if (free_fun)
			dd_vector_reset(vec, free_fun) ;

		if(vec->ptr) 
			__do_destroy(vec->ptr) ;

		__do_destroy(vec) ;
	}
}

DD_INT dd_vector_count(const dd_vector* vec) 
{
    return vec ? vec->count : 0 ;
}

void* dd_vector_get(const dd_vector* vec, DD_INT index) 
{
	if (vec && index < vec->count)
		return *(vec->ptr + index) ;

	return DD_NULL ;
}

void dd_vector_set(dd_vector* vec, DD_INT index, void* data)
{
	if (vec && index < vec->count) 
		*(vec->ptr + index) = data ;
}

void dd_vector_append(dd_vector* vec, void* data) 
{
	if (vec->count == vec->alloc_size) 
		_expand_to(vec, vec->count + vec->granularity) ;

	vec->count++ ;
	dd_vector_set(vec, vec->count - 1, data) ;
}

void dd_vector_insert(dd_vector* vec, DD_INT insert_index, void* data) 
{
	if ( vec->count == vec->alloc_size ) 
		_expand_to( vec, vec->count + vec->granularity ) ;

	if ( insert_index >= vec->count ) {
		vec->count++ ;
		dd_vector_set( vec, vec->count - 1, data ) ;
	}
	else {
		DD_MEMMOVE(vec->ptr + insert_index + 1, vec->ptr + insert_index, (vec->count - insert_index) * sizeof(void*));
		*(vec->ptr + insert_index) = data ;
		vec->count++ ;
	}
}

void dd_vector_expand(dd_vector* vec, DD_INT expand_size) 
{
	DD_INT newSize = vec->count + expand_size ;

	if ( newSize > vec->alloc_size )
		_expand_to( vec, newSize ) ;

	vec->count += expand_size ;
}

void dd_vector_reset(dd_vector* vec, void (*free_fun)(void*)) 
{
	if ( vec->count != 0 && free_fun ) {
		DD_INT i = 0 ; 
		for ( ; i < vec->count; i++ )
			free_fun(dd_vector_get(vec, i)) ;
	}

	vec->count = 0 ;
}


DD_INT dd_vector_find(dd_vector* vec, void* data) 
{
	DD_INT i = 0 ;
	for ( ; i < vec->count; i++ ) {
		if ( data == dd_vector_get( vec, i) )
			return i ;
	}

	return -1 ;
}

void* dd_vector_delete_by_index(dd_vector* vec, DD_INT index)
{
	void* delElement = DD_NULL ;

	if(vec && index < vec->count) {
		delElement = *(vec->ptr + index) ;
		*(vec->ptr + index) = DD_NULL;
		DD_MEMMOVE(vec->ptr + index, vec->ptr + index + 1, (vec->count - (index + 1)) * sizeof(void*));
		*(vec->ptr + vec->count - 1) = DD_NULL;
		vec->count-- ;
	}

	return delElement ;
}

void* dd_vector_delete(dd_vector* vec, void* data)
{
	DD_INT index = dd_vector_find(vec, data) ;
	
	if ( index == -1 )
		return DD_NULL ;

	return dd_vector_delete_by_index(vec, index) ;
}


void dd_vector_swap(dd_vector* vec, DD_UINT index1, DD_UINT index2) 
{
    void* tmp = DD_NULL ;

    __DD_ASSERT_DEFENSE(vec && index1 < (DD_UINT)vec->count && index2 < (DD_UINT)vec->count, return) ;

    tmp = *(vec->ptr + index1);
    *(vec->ptr + index1) = *(vec->ptr + index2) ;
    *(vec->ptr + index2) = tmp ;
}


void dd_vector_insert_by(dd_vector* vec, void* data, DD_INT (*compare)(const void*, const void*)) 
{   
    /* Binary search for the insert operation */
    if (vec && compare) {

        DD_INT start = 0 ;
        DD_INT end   = dd_vector_count(vec) - 1 ;
        DD_INT mid   = 0 ;
        DD_INT cmp   = -1 ;
        
        while(start <= end) {
            
            mid = start + (end - start) / 2 ;
            
            cmp = compare(data, dd_vector_get(vec, mid)) ; 
            
            if (cmp == 0) {
                dd_vector_insert(vec, mid, data) ;
                return ;
            }
            
            if (cmp < 0)
                end = mid - 1 ;
            else 
                start = mid + 1 ;
            
        }
        
        __DD_ASSERT((start == end + 1) && (end < dd_vector_count(vec))) ;
        
        if (cmp < 0) 
            dd_vector_insert(vec, mid, data) ;
        else 
        dd_vector_insert(vec, mid + 1, data) ; 
    }
}


DD_INT dd_vector_find_by_key(dd_vector* vec, const void* key, DD_INT (*compare)(const void*, const void*))
{
    if (vec && compare) {

        DD_INT start = 0 ;
        DD_INT end   = dd_vector_count(vec) - 1 ;
        DD_INT mid   = 0 ;
        DD_INT cmp   = -1 ;
        
        while(start <= end) {
            
            mid = start + (end - start) / 2 ;
            
            cmp = compare(key, dd_vector_get(vec, mid)) ; 
            
            if (cmp == 0)
                return mid ;
            
            if (cmp < 0)
                end = mid - 1 ;
            else 
                start = mid + 1 ;
        }
    }

    return -1 ;
}

void* dd_vector_delete_by_key(dd_vector* vec, const void* key, DD_INT (*compare)(const void*, const void*)) 
{
    DD_INT findex = dd_vector_find_by_key(vec, key, compare) ;

    if (findex != -1)
        return dd_vector_delete_by_index(vec, findex) ;

    return DD_NULL ;
}


void dd_vector_sort(dd_vector* vec, DD_INT (*compare)(const void*, const void*)) 
{
    if ( vec && (vec->count > 1) && compare ) {
        DD_INT count = vec->count ;
        DD_INT i = 0 ;  
        void* data = DD_NULL ;
        
        vec->count =  0 ;
        
        for (; i < count; i++) {
            data = dd_vector_getfast(vec, i) ;
            dd_vector_insert_by(vec, data, compare) ;
        }
        
        __DD_ASSERT(vec->count == count) ;
    }
}


#ifdef __DD_UNITTEST

#define __TEST_APPEND_TIMES		2000
#define __TEST_INSERT_INDEX		1500
#define __TEST_INSERT_TIMES		1000

#define __TEST_INSERT_BY_TIMES  (10000 + 1)


static DD_INT _ut_compare(const void* data1, const void* data2)
{
    DD_INT val1 = (DD_INT)data1 ;
    DD_INT val2 = (DD_INT)data2 ;
    
    if (val1 == val2)  return 0 ;
    
    if (val1 < val2)  return -1 ;
        
    return 1 ;
}

static DD_INT _ut_compare_ptr(const void* data1, const void* data2)
{
    DD_INT val1 = *((DD_INT*)data1) ;
    DD_INT val2 = *((DD_INT*)data2) ;
    
    if (val1 == val2)  return 0 ;
    
    if (val1 < val2)  return -1 ;
    
    return 1 ;
}

static DD_BOOL _ut_check_sorted_vec(const dd_vector* vec, DD_INT (*compare)(const void*, const void*)) 
{
    DD_INT i = 0 ;
    for (; i < dd_vector_count(vec) - 1; i++){
        
        if (compare(dd_vector_get(vec, i), dd_vector_get(vec, i+1)) > 0)
            return DD_FALSE ;
    }

    return DD_TRUE ;
}


DD_BOOL dd_vector_test() 
{
	dd_vector* vec = dd_vector_create(10) ;
    dd_vector* sorted_vec = dd_vector_create(10) ;
	DD_INT i = 0 ;
	DD_INT insert_index = __TEST_INSERT_INDEX;
	DD_INT del_count	= 0 ;

	/* Test append */
	for ( ; i < __TEST_APPEND_TIMES; i++ ) {
		DD_INT* tmp = DD_MALLOC(sizeof(DD_INT)) ;
		*tmp = i ;
		dd_vector_append(vec, tmp) ;
	}

	if ( dd_vector_count(vec) != __TEST_APPEND_TIMES )
		return DD_FALSE ;

	for ( i = 0 ; i < __TEST_APPEND_TIMES ; i++ ) {
		DD_INT tmp = *((DD_INT*)(dd_vector_get(vec, i))) ;
		if ( tmp != i )
			return DD_FALSE ;
	}

	/* Test insert */
	for ( i = 0; i < __TEST_INSERT_TIMES; i++ ) {
		DD_INT* tmp = DD_MALLOC(sizeof(DD_INT)) ;
		*tmp = __TEST_INSERT_TIMES + i ;
		dd_vector_insert(vec, insert_index, tmp);
		insert_index++ ;
	}

	if ( dd_vector_count(vec) != (__TEST_INSERT_TIMES + __TEST_APPEND_TIMES) )
		return DD_FALSE ;

	insert_index = __TEST_INSERT_INDEX; 
	for ( i = 0 ; i < insert_index ; i++ ) {
		DD_INT tmp = *((DD_INT*)(dd_vector_get(vec, i))) ;
		if ( tmp != i )
			return DD_FALSE ;
	}

	for ( ; i < (insert_index + __TEST_INSERT_TIMES); i++ ) {
		DD_INT tmp = *((DD_INT*)(dd_vector_get(vec, i))) ;
		if ( tmp != __TEST_INSERT_TIMES + (i - insert_index) )
			return DD_FALSE ;
	}
	
	for ( ; i < __TEST_INSERT_TIMES + __TEST_APPEND_TIMES; i++ ) {
		DD_INT tmp = *((DD_INT*)(dd_vector_get(vec, i))) ;
		if ( tmp != i - __TEST_INSERT_TIMES )
			return DD_FALSE ;
	}

	/* Test Delete */
	DD_SRAND((DD_UINT)DD_TIME(0)) ;
	for (i = 0 ;i < dd_vector_count(vec); i++) {
		if (DD_RAND() % 3 == 0) {
			dd_vector_delete_by_index(vec, i) ;
			del_count++ ;
		}
	}

	if ( dd_vector_count(vec) != (__TEST_INSERT_TIMES + __TEST_APPEND_TIMES - del_count) )
		return DD_FALSE ;

    dd_vector_reset(vec, DD_FREE) ;
    
    i = 0 ;
    DD_SRAND((DD_UINT)DD_TIME(0)) ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        DD_INT* tmp = DD_MALLOC(sizeof(DD_INT)) ;
		*tmp =  DD_RAND() ;
        dd_vector_append(vec, (void*)tmp) ;

        dd_vector_insert_by(sorted_vec, (void*)(*tmp), _ut_compare) ;

        if (!_ut_check_sorted_vec(sorted_vec, _ut_compare)) 
            return DD_FALSE ;
    }
    
    i = 0 ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        DD_INT* tmp   = (DD_INT*)dd_vector_get(vec, i) ;
        DD_INT findex = dd_vector_find_by_key(sorted_vec, (void*)(*tmp), _ut_compare) ;
        
        if (findex == -1 || *tmp != (DD_INT)dd_vector_get(sorted_vec, findex))
            return DD_FALSE ;
    }

    dd_vector_sort(vec, _ut_compare_ptr) ;

    if (!_ut_check_sorted_vec(vec, _ut_compare_ptr))
            return DD_FALSE ;

    i = 0 ;
    for (; i < __TEST_INSERT_BY_TIMES; i++) {
        DD_INT* tmp   = (DD_INT*)dd_vector_get(vec, i) ;
        if (*tmp != (DD_INT)dd_vector_get(sorted_vec, i))
            return DD_FALSE ;
    }


	dd_vector_destroy(vec, DD_FREE) ;
    dd_vector_destroy(sorted_vec, DD_NULL) ;

	return DD_TRUE ;
}


void dd_vector_dump_file(const dd_vector* vec, const DD_CHAR* file_name) 
{
    FILE* file = fopen(file_name, "wb") ;

    fwrite(vec, sizeof(dd_vector), 1, file) ;

    fwrite(vec->ptr, vec->count * sizeof(void*), 1, file) ;

    fclose(file) ;
}

dd_vector* dd_vector_read_file(const DD_CHAR* file_name) 
{
    dd_vector* vec =  dd_vector_create(5) ;
    
    FILE* file = fopen(file_name, "rb") ;
    
    DD_FREE(vec->ptr) ;

    fread(vec, sizeof(dd_vector), 1, file) ;

    vec->ptr = (void**)DD_MALLOC(vec->alloc_size * sizeof(void*)) ;

    fread(vec->ptr, vec->count * sizeof(void*), 1, file) ;

    fclose(file) ;

    return vec ;
}

#endif	/* __DD_UNITTEST */


/* End of File */
